Estimating quantiles is one of the most basic problems in data sketching. In this problem, a stream x1, x2, x3, …, xn of elements from some universe of size U, a rank r, and an accuracy ε are given. The goal is to give a space-efficient algorithm that outputs an element with rank between r-εn and r+εn. For example, this captures median estimation and 99th percentile estimation.

It has long been known that a quantile sketch can be made more space-efficient than storing every element individually (which would take nlogU memory). The previous best algorithms all improved substantially on nlogU but did not meet the lower bound of Ω(ε^{-1}·(logεn+logεU)) . In this talk, I’ll describe a deterministic quantile sketch that uses the optimal O(ε^{-1}·(logεn+logεU)) bits of memory.